#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// 1248. 统计「优美子数组」
class Solution
{
public:
    int numberOfSubarrays(vector<int>& nums, int k) 
    {
        for(int& x : nums)
        {
            x = x % 2;
        }

        unordered_map<int, int> m;
        m[0] = 1;
        int prev = 0, ret = 0;
        for(int x : nums)
        {
            prev += x;
            if(m.count(prev - k)) ret += m[prev - k];
            ++m[prev];
        }
        return ret;
    }
};

// 1712. 将数组分成三个子数组的方案数
class Solution 
{
public:
    int waysToSplit(vector<int>& nums) 
    {
        int n = nums.size(), MOD = 1e9 + 7;
        for(int i = 1; i < n; ++i) nums[i] += nums[i - 1];

        long long ret = 0;
        for(int i = 0, j = 1, k = 1; i < n - 2 && 3 * nums[i] <= nums[n - 1]; ++i)
        {
            j = max(i + 1, j);
            while(j < n - 1 && nums[j] < 2 * nums[i]) ++j;
            while(k < n - 2 && nums[k + 1] <= (nums[n - 1] + nums[i]) / 2) ++k;
            ret += k - j + 1;
        }
        return ret % MOD;
    }
};

// 2444. 统计定界子数组的数目
class Solution 
{
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) 
    {
        long long ret = 0;
        int n = nums.size(), min_i = -1, max_i = -1, i0 = -1;
        for(int i = 0; i < n; ++i)
        {
            int x = nums[i];
            if(x == minK) min_i = i;
            if(x == maxK) max_i = i;
            if(x < minK || x > maxK) i0 = i;
            ret += max(min(min_i, max_i) - i0, 0);
        }
        return ret;
    }
};

// 992. K 个不同整数的子数组
class Solution 
{
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) 
    {
        int n = nums.size();
        // 返回最多 m 个不同整数的子数组
        auto f = [&](int m){
            int left = 0, right = 0, ret = 0;
            unordered_map<int, int> cnt;
            while(right < n)
            {
                ++cnt[nums[right]];
                while(cnt.size() > m)
                {
                    --cnt[nums[left]];
                    if(cnt[nums[left]] == 0) cnt.erase(nums[left]);
                    ++left;
                }
                ret += right - left + 1;
                ++right;
            }
            return ret;
        };
        return f(k) - f(k - 1);
    }
};

// 188. 买卖股票的最佳时机 IV
class Solution 
{
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        int n = prices.size();
        k = min(k, n / 2);
        vector<vector<int>> f(n, vector<int>(k + 1, -0x3f3f3f3f));
        auto g = f;
        f[0][0] = -prices[0], g[0][0] = 0;
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j <= k; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j >= 1)
                {
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int ret = 0;
        for(int i = 0; i <= k; ++i)
        {
            ret = max(ret, g[n - 1][i]);
        }
        return ret;
    }
};

// 1433. 检查一个字符串是否可以打破另一个字符串
class Solution 
{
public:
    bool checkIfCanBreak(string s1, string s2) 
    {
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        bool flag1 = false, flag2 = false;
        int n = s1.size();
        for(int i = 0; i < n; ++i)
        {
            if(s1[i] == s2[i]) continue;
            if(s1[i] > s2[i]) flag1 = true;
            else flag2 = true;
        }
        if(flag1 && flag2) return false;
        return true;
    }
};

// 1701. 平均等待时间
class Solution 
{
public:
    double averageWaitingTime(vector<vector<int>>& customers) 
    {
        double sum = 0;
        int n = customers.size();
        int begin = customers[0][0];
        for(int i = 0; i < n; ++i)
        {
            begin = max(begin, customers[i][0]);
            sum += begin - customers[i][0] + customers[i][1];
            begin += customers[i][1];
        }
        return sum / n;
    }
};

// 845. 数组中的最长山脉
class Solution 
{
public:
    int longestMountain(vector<int>& arr) 
    {
        int n = arr.size();;

        vector<int> right(n);
        for(int i = n - 2; i >= 0; --i)
        {
            right[i] = (arr[i + 1] < arr[i] ? right[i + 1] + 1 : 0);
        }

        int ret = 0;
        vector<int> left(n);
        for(int i = 1; i < n; ++i)
        {
            left[i] = (arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0);
            if(left[i] > 0 && right[i] > 0)
            {
                ret = max(ret, left[i] + right[i] + 1);
            }               
        }
        return ret;
    }
};